809. Squares and
Rounds
I hear,
brother, the war will be,
Cold, wet,
long and wicked.
The Squares
will fight against Rounds
Because
they are smooth.
Ensemble “Skryabin”
The leader
of Squares, being in the heat of passion, gave to each of his fighters so large
dose of Ozverin (its a type of drug) that each of them first attack, and then
decides, does he attack a Square or Round person. Rounds never know how to
fight hand to hand, but they possess some magic tricks.
The troop
of s Squares attacked the village where r Rounds lived. As a
consequence of Ozverin imposition and magic tricks of Rounds, it appeared that
the fight takes place by such rules. Every minute, a randomly pair of creatures
is chosen, and:
·
if Round and Square are chosen, the Square kills the
Round and fights further;
·
if two Rounds are chosen, they apologize to each other
and fight further;
·
if two Squares are chosen, they kill each other.
The pair is
chosen uniformly at random among all living creatures, so that there were two
different beings (possibly the same species). For example, when two Squares and
one Round are alive, then with equal probability of 1/3 the fight takes place
between the
Find the
probability that under these fight rules at least one Round will survive, and
all Squares will die.
Input. Two integers are given in one line
- the number of Squares s (1 ≤ s ≤ 2010) and the number of Rounds
r (1 ≤ r ≤ 2010).
Output. Print one
number - the required probability (with a relative error less than 10-9).
|
Sample input |
Sample output |
|
2 20 |
0.80545497225 |
SOLUTION
dynamic programming + probability
Algorithm analysis
From the problem statement we can conclude
that the Squares die only in pairs. So if s is odd, the answer is 0.
Let p(s, r)
be the probability that all Squares will die, but at least one Round will
survive. It is
obvious that p(s, 0) = 0 for any s
≥ 0 and p(0, r) = 1 for any r ≥ 1.
Let now s Squares and r Rounds are alive. Then we can choose 
= 
pairs among them. Out
of this amount s * r pairs are «Round - Square», 
= 
pairs are «Square - Square»
and 
= 
pairs are «Round - Round».
According to the formula of total probability we obtain
p(s, r) = 
+ 
+ 
Multiply the equation by and reduce:
p(s, r) 
= 
+ 
or the same as
p(s, r) = 
Example
Consider the test where s = 2, r = 1. To calculate
p(2, 1) we need p(2, 0) and p(0, 1). Note
that p(2, 0) = 0 and p(0, 1) = 1.Then
p(2, 1) = 
= 
= 
Algorithm realization
The recursive implementation of the
program will give the Time Limit, so we need to write a cyclic. Store the
probability values p(i, j) in the cells of array res[i][j].
#define MAX 2011
#define EPS 1e-7
double res[MAX][MAX];
The main part of the program. Read the input data. Initialize
res[i][0] = 0 for i ≥ 0 and res[0][j] = 1 for j ≥ 1.
scanf("%d %d",&s,&r);
memset(res,0,sizeof(res));
for(i = 1; i < MAX; i++) res[0][i] =
1;
Recalculate the values of res[i][j]
according to the formula given in problem explanation.
for(i = 1; i <= s; i++)
for(j = 1; j <= r; j++)
{
res[i][j] = 2 * i * j * res[i][j-1] +
i * (i - 1) * ((i > 1) ?
res[i-2][j] : 0);
res[i][j] /= ((i + j) * (i + j - 1) - j * (j
- 1));
}
Print the answer.
printf("%.11lf\n",res[s][r]);